//解法一:
暴力解法(暴力查找对应的位置,找是否有比它大的数)
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] arr = new int[nums1.length];
        for(int i = 0; i < nums1.length; i++){
            int ret = findRFMax(nums2,findIndex(nums2,nums1[i]));
            arr[i] = ret;
        }
        return arr;
    }

    public int findRFMax(int[] arr,int index){
        for(int i = index; i < arr.length-1;i++){
            if(arr[index] < arr[i+1]){
                return arr[i+1];
            }
        }
        return -1;
    }

    public int findIndex(int[] arr,int key){
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == key){
                return i;
            }
        }
        return -1;
    }
}

//解法二:使用栈和HashMap正序遍历
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int num : nums2){
            while(!stack.isEmpty() && stack.peek() < num){
                map.put(stack.pop(),num);
            }
            stack.push(num);
        }
        int[] ret = new int[nums1.length];
        for(int i = 0; i < nums1.length; i++){
            ret[i] = map.getOrDefault(nums1[i],-1);
        }
        return ret;
    }
}

//解法三:使用单调栈(逆序遍历)和HashMap
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = nums2.length-1; i >= 0; i--){
            while(!stack.isEmpty() && nums2[i] >= stack.peek()){
                stack.pop();
            }
            map.put(nums2[i],stack.isEmpty()?-1:stack.peek());
            stack.push(nums2[i]);
        }
        int[] ret = new int[nums1.length];
        for(int i = 0; i < ret.length; i++){
            ret[i] = map.get(nums1[i]);
        }
        return ret;
    }
}